package weka.classifiers.rules;

import java.io.Serializable;
import java.util.Collections;
import java.util.Enumeration;
import java.util.HashMap;
import java.util.LinkedList;
import java.util.List;
import java.util.Map;
import java.util.Vector;
import java.util.concurrent.ExecutorService;
import java.util.concurrent.Executors;

import weka.classifiers.AbstractClassifier;
import weka.classifiers.Evaluation;
import weka.core.AdditionalMeasureProducer;
import weka.core.Attribute;
import weka.core.Capabilities;
import weka.core.CapabilitiesHandler;
import weka.core.Drawable;
import weka.core.FastVector;
import weka.core.Instance;
import weka.core.Instances;
import weka.core.Option;
import weka.core.OptionHandler;
import weka.core.RevisionUtils;
import weka.core.SelectedTag;
import weka.core.Summarizable;
import weka.core.Tag;
import weka.core.TechnicalInformation;
import weka.core.TechnicalInformationHandler;
import weka.core.Utils;
import weka.core.WeightedInstancesHandler;
import weka.core.Capabilities.Capability;
import weka.core.TechnicalInformation.Field;
import weka.core.TechnicalInformation.Type;

/**
 * <p>Title: Weka</p>
 *
 * <p>Description: weka.classifiers.rules.JChipper </p>
 *
 * <p>Copyright: Copyright (c) 2009</p>
 *
 * <p>Company: H�gskolan i Bor�s</p>
 *
 * @author Tuve L�fstr�m
 * @version 1.0
 *
 * 
 */
public class JChipper extends AbstractClassifier implements
        OptionHandler,
        Serializable,
        CapabilitiesHandler,
        //Drawable, /* M�jligg�r att reglerna ritas ut som tr�d, m�ste implementeras i DOT-spr�ket...*/
        //Matchable, /* M�jligg�r att olika tr�d kan j�mf�ras med varandra, inte givet hur det skall implementeras... */
        //Sourcable, /* M�jligg�r att en regel konverteras till javakod */
        WeightedInstancesHandler, /* Anger att klassen anv�nder sig av instansvikter, vilket v�l inte �r fallet? */
        Summarizable,
        /* M�jligg�r att klassen exporterar en kortfattad beskrivning av sig sj�lv */
        AdditionalMeasureProducer, /* M�jligg�r att till�ta extra utv�rderingskriterier, t ex l�ngd, djup och fitness. Vilka fler? */
        TechnicalInformationHandler {

    private boolean m_useInterval = false;
    private double m_ignoreVal = 0.05; //[1 0.1;0.1 1]; Fr�gan �r hur detta skall implementeras. F�rslagsvis s� anv�nds en enkel kostvariabel som har ett v�rde som default, sedan kan man m�jligen l�gga till en advanced feature med en kostvariabel som i matlab implementationen?
    private double m_stop = 0.95; //Proportion of instances to classify before stop
    private Vector m_Model = null;
    private int m_numDisjunctions = 0;
    private int m_numConjunctions = 0;
    private double[] priorDist;
    private double m_numInstances = 0;
    private String[] m_ClassNames;

    public static final Tag[] TAGS_ruleSel = {
    new Tag(0, "Covarege"),
    new Tag(1, "Accuracy"),
    new Tag(2, "Laplace"),
    new Tag(3, "M-estimate"),
    new Tag(4, "FOIL")
  };

    public static final Tag[] TAGS_ignoreSel = {
    new Tag(0, "IRI", "Ignore as percentage of remaining instances"),
    new Tag(1, "IAN", "Ignore as absolute number"),
    new Tag(2, "IPD", "Ignore as percentage of dataset"),
    new Tag(3, "IRA", "Ignore as rule accuracy")
  };
    public int m_ruleSelChoice = 1;
    public int m_ignoreSelChoice = 0;
    private boolean m_Debug = false;
	private boolean m_beGreedy;
	private Instances m_data;
	private boolean m_useMajorityAsDefault = true;
	private int m_majorityClass = -1;

    public String getRevision() {
        return RevisionUtils.extract("$Revision: 1.0 $");
    }

    /**
     * Returns an instance of a TechnicalInformation object, containing
     * detailed information about the technical background of this class,
     * e.g., paper reference or book this class is based on.
     *
     * @return the technical information about this class
     */
    @Override
    public TechnicalInformation getTechnicalInformation() {
        TechnicalInformation result;

        result = new TechnicalInformation(Type.INPROCEEDINGS);
        result.setValue(Field.AUTHOR, "Cecilia S�nstr�d");
        //result.setValue(Field.TITLE, "Chipper...");
        //result.setValue(Field.BOOKTITLE, "Twelfth International Conference on Machine Learning");
        //result.setValue(Field.YEAR, "2008");
        //result.setValue(Field.PAGES, "115-123");
        //result.setValue(Field.PUBLISHER, "Morgan Kaufmann");

        return result;
    }

    private int numConditions() {
        int numConditions = 0;
        for (int j = 0; j < m_Model.size(); j++) {
            JChipperRule rule = (JChipperRule) m_Model.elementAt(j);
            numConditions += rule.numConditions();
        }
        return numConditions;
    }

    /**
     * Four types of Chipper rules are implemented.
     * 1. A simple rule with one condition
     * 2. An interval rule with two conditions, where the conditions
     *    represents an interval for one attribute
     * 3. A series of disjunctive Chipper rules
     * 4. A default rule, without condition
     *
     * There are also three types of conditions (<=, >=, and ==)
     */
    private class JChipperRule implements Serializable, Comparable<JChipperRule> {

        protected Attribute attr = null;
        protected double value = -1;
        protected boolean fromTop = true;
        protected double classIndex = -1;
        protected double numCovered = -1;
        protected double numCorrect = -1;
        protected double[] classDist = null;
        protected boolean isSubRule = false;
        protected boolean isConjunctive = false;
        protected boolean isInterval = false;
        protected List<JChipperRule> subRules = null;
        protected double laplace = -1, m_estimate = -1, foil = -1;

        /** Constructor for default rules */
        private JChipperRule(int clIndex, double correct, double covered, double[] clDist) {
            classIndex = clIndex;
            numCovered = covered;
            classDist = normalizeClassDistribution(clDist);
            numCorrect = correct;
        }

        /** Constructor for a normal Chipper rule */
        private JChipperRule(Attribute splitAttr, double splitValue, boolean splitType, double clIndex, double correct, double covered, double[] clDist) {
            attr = splitAttr;
            value = splitValue;
            fromTop = splitType;
            classIndex = clIndex;
            numCovered = covered;
            classDist = normalizeClassDistribution(clDist);
            numCorrect = correct;
        }

        /** Constructor for building composite Chipper rules */
        private JChipperRule(JChipperRule rule) {
            classIndex = rule.classIndex;
            addSubRule(rule, rule.numCorrect, rule.numCovered, rule.classDist);
        }

        /** Constructor for interval rules */
        private JChipperRule(JChipperRule from, JChipperRule to, double correct, double covered, double[] clDist, boolean interval) {
            isConjunctive = true;
            this.isInterval = interval;
            /*from.isInterval = interval;
            to.isInterval = interval;*/
            classIndex = from.classIndex;
            addSubRule(from, correct, covered, clDist);
            addSubRule(to, correct, covered, clDist);
        }

        private void addSubRule(JChipperRule subRule, double correct, double covered, double[] clDist) {
            if (subRules == null) {
                subRules = new LinkedList<JChipperRule>();
            }
            subRule.isSubRule = true;
            subRules.add(subRule);
            numCovered = covered;
            classDist = normalizeClassDistribution(clDist);
            numCorrect = correct;
        }

        @Override
        protected JChipperRule clone() {
            JChipperRule copy = new JChipperRule(this.attr, this.value, this.fromTop, this.classIndex, this.numCorrect, this.numCovered, this.classDist);
            if (subRules != null) {
                copy.subRules = new LinkedList<JChipperRule>(this.subRules);
            }
            copy.isSubRule = this.isSubRule;
            copy.isConjunctive = this.isConjunctive;
            copy.isInterval = this.isInterval;
            return copy;
        }

        @Override
        public int compareTo(JChipperRule rule) {
            if (this.betterThan(rule)) {
                return 1;
            } else if (rule.betterThan(this)) {
                return -1;
            } else {
                return 0;
            }
        }

        private boolean betterThan(JChipperRule rule) {
            if (rule == null) {
                return true;
            }
            switch (m_ruleSelChoice) {
                case 0: //coverage
                    if (numCovered == rule.numCovered) {
                        if (numCorrect == rule.numCorrect) {
                            return numConditions() < rule.numConditions();
                        } else {
                            return numCorrect > rule.numCorrect;
                        }
                    } else
                        return numCovered > rule.numCovered;
                case 1: //accuracy, i.e. highest number of correct
                    if (numCorrect == rule.numCorrect) {
                        if (numCovered == rule.numCovered) {
                            return numConditions() < rule.numConditions();
                        } else {
                            return numCovered > rule.numCovered;
                        }
                    } else
                        return numCorrect > rule.numCorrect;
                case 2: //laplace
                    if (getLaplace() == rule.getLaplace()) {
                        return numConditions() < rule.numConditions();
                    } else
                        return getLaplace() > rule.getLaplace();
                case 3: //m-estimate
                    if (getMEstimate() == rule.getMEstimate()) {
                        return numConditions() < rule.numConditions();
                    } else
                        return getMEstimate() > rule.getMEstimate();
                case 4: //foil
                    if (getFOIL() == rule.getFOIL()) {
                        return numConditions() < rule.numConditions();
                    } else
                        return getFOIL() > rule.getFOIL();
            }
            return true;
        }

        public double getLaplace() {
            if (laplace == -1) {
                double f = classDist[(int) classIndex] * numCovered;
                laplace = (f + 1) / (numCovered + classDist.length);
            }
            return laplace;
        }

        public double getMEstimate() {
            if (m_estimate == -1) {
                double f = classDist[(int) classIndex] * numCovered;
                m_estimate = (f + (classDist.length * priorDist[(int) classIndex])) / (numCovered + classDist.length);
            }
            return m_estimate;
        }

        public double getFOIL() {
            if (foil == -1) {
                double p1 = classDist[(int) classIndex] * numCovered,
                        n1 = numCovered - p1,
                        p0 = priorDist[(int) classIndex] * m_numInstances,
                        n0 = m_numInstances - p0;
                foil = p1 * (Utils.log2(p1 / (p1 + n1)) - Utils.log2(p0 / (p0 + n0)));
            }
            return foil;
        }

        
        public boolean covers(Instance instance) {
            if (isConjunctive()) {
                boolean covers = true;
                for (JChipperRule rule : subRules) {
                    covers &= rule.covers(instance);
                }
                return covers;
            }
            if (isDisjunctive()) {
                boolean covers = false;
                for (JChipperRule rule : subRules) {
                    covers |= rule.covers(instance);
                }
                return covers;
            }
            if (isDefault()) {
                return true;
            } else if (attr.isNominal()) {
                return (instance.value(attr) == value);
            } else if (fromTop) {
                return (instance.value(attr) >= value);
            } else {
                return (instance.value(attr) <= value);
            }
        }

        public double classify(Instance instance) {
            if (covers(instance)) {
                return classIndex;
            }
            return -1;
        }

        private double[] getDistribution(Instance instance) {
            if (covers(instance)) {
                if (classDist == null) {
                    double[] doubles = new double[instance.numClasses()];
                    for (int i = 1; i < instance.numClasses(); i++) {
                        doubles[i] = 0;
                    }
                    doubles[(int) classIndex] = 1;
                    return doubles;
                } else {
                    return classDist;
                }
            }
            return null;
        }

        @Override
        public String toString() {
            String rule;
            /** Disjunctive rules should probably be handled in conditionToString
             *  To enable printing of arbitrarily nested rules */
            if (isSubRule) {
                rule = conditionToString();
            } else if (isDefault()) {
                rule = "\nDEFAULT: " + m_ClassNames[(int)classIndex] + " ";
                //rule = "\ndefault: " + classIndex;
            } else {
                rule = "\nIF" + conditionToString() + "THEN " + m_ClassNames[(int)classIndex] + " ";
                //rule = "\n" + conditionToString() + "==> " + classIndex + " ";
            }
            return rule + "[" + (int) numCovered + "/" + (int) (numCovered - numCorrect) + "]";
        }

        private String conditionToString() {
            String rule = "";
            /** Handle nested rules here instead of in toString */
            if (isInterval)
                return " " + subRules.get(0).attr.name() + " WITHIN " + subRules.get(0).value + " AND " + subRules.get(1).value + " ";
                //return " " + subRules.get(0).attr.name() + " == [ " + subRules.get(0).value + ", " + subRules.get(1).value + " ] ";
            if (isDisjunctive()) {
                int i;
                for (i = 0; i < numSubRules()-1; i++) {
                    rule += " (" + subRules.get(i).toString() + ")\n\tOR";
                    //rule += "(" + subRules.get(i).toString() + ")\n\t|| ";
                }
                rule += " (" + subRules.get(i).toString() + ")\n\t";
                return rule;
            } else if (isConjunctive()) {
                rule += "" + subRules.get(0).conditionToString() + " ";
                for (int i = 1; i < numSubRules(); i++) {
                    rule += "AND " + subRules.get(i).conditionToString() + "";
                    //rule += "&& " + subRules.get(i).conditionToString() + " ";
                }
                return rule;
            } else if (attr.isNominal()) {
                return " " + attr.name() + " == " + value + " ";
            } else if (fromTop) {
                return " " + attr.name() + " >= " + value + " ";
            } else {
                return " " + attr.name() + " <= " + value + " ";
            }
        }

        public boolean isDefault() {
            return !isConjunctive() && !isDisjunctive() && attr == null;
        }

        private boolean isDisjunctive() {
            return !isConjunctive() && subRules != null;
        }

        private boolean isConjunctive() {
            return isConjunctive;
        }

        private double[] normalizeClassDistribution(double[] clDist) {
            if (clDist == null) {
                return null;
            }
            double sum = 0;
            for (int i = 0; i < clDist.length; i++) {
                sum += clDist[i];
            }
            double[] doubles = new double[clDist.length];
            for (int i = 0; i < clDist.length; i++) {
                doubles[i] = clDist[i] / sum;
            }
            return doubles;
        }

        private int numSubRules() {
            if (subRules == null) {
                return 0;
            }
            return subRules.size();
        }

        private int numConditions() {
            int numConditions = 0;
            if (isDisjunctive() || isConjunctive()) {
                for (JChipperRule rule : subRules) {
                    numConditions += rule.numConditions();
                }
            } else {
                numConditions = 1;
            }
            return numConditions;
        }
    }

    private boolean acceptableRule(double numCorrect, double numCovered, double numInstances) {
        double ignoreNum = 0;
		switch (m_ignoreSelChoice) {
			case 0: ignoreNum = numInstances * m_ignoreVal; break;
			case 1: ignoreNum = m_ignoreVal; break;
			case 2: ignoreNum = m_data.numInstances() * m_ignoreVal; break;
			case 3: ignoreNum = numCovered - m_ignoreVal * numCovered; break;
		}

		// numCovered > 0 &&
		// numCorrect > numCovered / m_data.numClasses() &&
		// numCovered - numCorrect <= numCorrect &&
		return numCovered - numCorrect <= ignoreNum;

    }

    private JChipperRule findBestRule(List<JChipperRule> rules) {
        if (rules == null || rules.size() == 0) {
            return null;
        }
        Collections.sort(rules);
        return rules.get(rules.size() - 1);
    }
    
    private List<JChipperRule> findConjunctiveRules(ExecutorService executor, List<JChipperRule> rules, Instances data) {
        if (rules == null || rules.size() == 0) {
            return null;
        }
        int i = rules.size();
        List<JChipperRule> conjunctiveRules = new LinkedList<JChipperRule>();
        List<JChipperRule> tmpRules = new LinkedList<JChipperRule>();
        for (int r = 0; r < rules.size(); r++) {
            JChipperRule rule = rules.get(r).clone();
            Instances covered = new Instances(data, data.numInstances());
            for (int j = 0; j < data.numInstances(); j++) {
                Instance inst = data.instance(j);
                if (rule.covers(inst)) {
                    covered.add(inst);
                }
            }
            tmpRules = findChipperRule(executor, covered, m_useInterval);
            Collections.sort(tmpRules);
            JChipperRule best = rule;
            for (i = tmpRules.size()-1; i >= 0; i--) {
                if (rule.classIndex == tmpRules.get(i).classIndex) {
                    double cov = 0;
                    double[] classDist = new double[data.numClasses()];
                    for (int j = 0; j < data.numClasses(); j++) {
                        classDist[j] = 0;
                    }
                    /** Calculate class distributions for instances covered by all
                     *  conjunctive rules, including current */
                    for (int j = 0; j < covered.numInstances(); j++) {
                        Instance inst = covered.instance(j);
                        if (rule.covers(inst) && tmpRules.get(i).covers(inst)) {
                            cov += inst.weight();
                            classDist[(int) inst.classValue()] += inst.weight();
                        }
                    }
                    /** Make sure the conjunctive rule inlcuding current is acceptable */
                    if (acceptableRule(classDist[(int) rule.classIndex], cov, data.sumOfWeights())) {
                        JChipperRule tmp = new JChipperRule(rule.clone(), tmpRules.get(i).clone(), classDist[(int) rule.classIndex], cov, classDist, false);
                        /** Make sure it is better to add the rule than not */
                        if (tmp.betterThan(best)) {
                            best = tmp;
                            //conjunctiveRules.add(tmp);
                        //} else if (!conjunctiveRules.contains(rule)){
                        //    conjunctiveRules.add(rule);
                        }
                    }
                }
            }
            conjunctiveRules.add(best);
        }
        if (conjunctiveRules != null)
            Collections.sort(conjunctiveRules);
        return conjunctiveRules;
    }

    private List<JChipperRule> findDisjunctiveRules(List<JChipperRule> rules, Instances data) {
        if (rules == null || rules.size() == 0) {
            return null;
        }
        int i = rules.size();
        Collections.sort(rules);
        /** Add all existing rules */
        List<JChipperRule> disjunctiveRules = new LinkedList<JChipperRule>(rules);
        /** For each rule, try to find acceptable disjunctive rules */
        for (int index = rules.size()-1; index >= 0; --index) {
            JChipperRule first = rules.get(index).clone(), best = new JChipperRule(first.clone());
            double cov = 0;
            /** Loop from best rule to worst */
            for (i = index- 1; i >= 0; i--) {
                if (best.numSubRules() >= getNumDisjunctions()+1) {
                    break;
                }
                if (first.classIndex == rules.get(i).classIndex) {
                    cov = 0;
                    double[] classDist = new double[data.numClasses()];
                    for (int j = 0; j < data.numClasses(); j++) {
                        classDist[j] = 0;
                    }
                    /** Calculate class distributions for instances covered by all
                     *  disjunctive rules, including current */
                    for (int j = 0; j < data.numInstances(); j++) {
                        Instance inst = data.instance(j);
                        if (best.covers(inst) || rules.get(i).covers(inst)) {
                            cov += inst.weight();
                            classDist[(int) inst.classValue()] += inst.weight();
                        }
                    }
                    JChipperRule tmp = best.clone();
                    /** Make sure the disjunctive rule inlcuding current is acceptable */
                    if (acceptableRule(classDist[(int) tmp.classIndex], cov, data.sumOfWeights())) {
                        tmp.addSubRule(rules.get(i).clone(), classDist[(int) tmp.classIndex], cov, classDist);
                        /** Make sure it is better to add the rule than not */
                        if (tmp.betterThan(best)) {
                            best = tmp;
                        //    disjunctiveRules.add(tmp);
                        //} else if (!disjunctiveRules.contains(first)) {
                        //    disjunctiveRules.add(first);
                        }
                    }
                }
            }
            if (best.betterThan(first)) {
                disjunctiveRules.add(best);
            } else {
                disjunctiveRules.add(first);
            }
        }
        if (disjunctiveRules != null)
            Collections.sort(disjunctiveRules);
        return disjunctiveRules;
    }

    private JChipperRule getDefaultRule(Instances localData) {
        /** Find default rule, i.e. an empty rule classifying majority class */
        double[] classDist = new double[localData.numClasses()];
        for (int i = 0; i < localData.numClasses(); i++) {
            classDist[i] = 0;
        }
        for (int i = 0; i < localData.numInstances(); i++) {
            classDist[(int) localData.instance(i).classValue()] += localData.instance(i).weight();
        }
        int defCl = 0;
        for (int i = 1; i < localData.numClasses(); i++) {
            if (classDist[i] > classDist[defCl]) {
                defCl = i;
            }
        }
        return new JChipperRule(defCl, classDist[defCl], localData.sumOfWeights(), classDist);
    }

    private Instances[] splitNominalData(Instances data, Attribute att) {
        int bag = att.numValues();
        Instances[] splitData = new Instances[bag];

        for (int x = 0; x < bag; x++) {
            splitData[x] = new Instances(data, data.numInstances());
        }

        for (int x = 0; x < data.numInstances(); x++) {
            Instance inst = data.instance(x);
            if (!inst.isMissing(att)) {
                int v = (int) inst.value(att);
                splitData[v].add(inst);
            }
        }
        return splitData;
    }

    private Instances[] splitNumericData(Instances data, Attribute att) {
    	// Map används för att indexera rätt bag, då kontinuerliga värden inte kan användas som index.
        Map<Double, Integer> map = new HashMap<Double, Integer>(data.numDistinctValues(att));

        int bag = data.numDistinctValues(att);
        Instances[] splitData = new Instances[bag];
        int count = 0;

        for (int x = 0; x < bag; x++) {
            splitData[x] = new Instances(data, data.numInstances());
        }

        for (int x = 0; x < data.numInstances(); x++) {
            Instance inst = data.instance(x);
            if (!inst.isMissing(att)) {
                int v;
                double key = inst.value(att);
                if (map.containsKey(key)) {
                    v = map.get(key).intValue();
                } else {
                    v = count++;
                    map.put(key, v);
                }
                splitData[v].add(inst);
            }
        }
        return splitData;
    }

    private List<JChipperRule> findAttributeSplit(Instances data, Attribute att, boolean useInterval) {
        List<JChipperRule> rules = new LinkedList<JChipperRule>();
        Instances localData = new Instances(data);
        localData.sort(att);
        localData.deleteWithMissing(att);
        Instances[] bags = null;
        if (att.isNominal()) {
            bags = splitNominalData(localData, att);
        } else {
            bags = splitNumericData(localData, att);
        }

        if (bags == null) {
            return null;
        }

        double[] classDist = new double[localData.numClasses()];
        JChipperRule best = null;
        double numCovered = 0;
        if (att.isNominal()) {
            /** For nominal attributes, find best bag */
            for (int i = 0; i < bags.length; i++) {
				if (!bags[i].isEmpty()) {
					numCovered = bags[i].sumOfWeights();
					for (int j = 0; j < localData.numClasses(); j++) {
						classDist[j] = 0;
					}
					for (int j = 0; j < bags[i].numInstances(); j++) {
						classDist[(int) bags[i].instance(j).classValue()] += bags[i]
								.instance(j).weight();
					}

					int clIndex = getClassIndex(classDist);
					// for (int clIndex = 0; clIndex < localData.numClasses();
					// clIndex++) {
					if (acceptableRule(classDist[clIndex], numCovered,
							localData.sumOfWeights())) {
						JChipperRule rule = new JChipperRule(att, bags[i]
								.instance(0).value(att), true, clIndex,
								classDist[clIndex], numCovered, classDist);
						if (rule.betterThan(best)) {
							best = rule;
						}
					}
					// }
				}
            }
            if (best != null) {
                rules.add(best);
            }
        } else {
            /**
             * For numeric attributes
             * Find best sequence of bags from bottom
             */
            for (int i = 0; i < localData.numClasses(); i++) {
                classDist[i] = 0;
            }
            for (int i = 0; i < bags.length; i++) {
                numCovered += bags[i].sumOfWeights();
                for (int j = 0; j < bags[i].numInstances(); j++) {
                    classDist[(int) bags[i].instance(j).classValue()] += bags[i].instance(j).weight();
                }
                int clIndex = getClassIndex(classDist);
                boolean stop = true;
                //for (int clIndex = 0; clIndex < localData.numClasses(); clIndex++) {
                    if (acceptableRule(classDist[clIndex], numCovered, localData.sumOfWeights())) {
                        JChipperRule rule = new JChipperRule(att, bags[i].instance(0).value(att), false, clIndex, classDist[clIndex], numCovered, classDist);
                        if (rule.betterThan(best)) {
                            best = rule;
                        }
                        stop = false;
                    }
                //}
                if (stop && m_beGreedy) {
                    break;
                }
            }
            if (best != null) {
                rules.add(best);
            }
            /** 
             * For numeric attributes 
             * Find best sequence of bags from top
             */
            best = null;
            for (int i = 0; i < localData.numClasses(); i++) {
                classDist[i] = 0;
            }
            numCovered = 0;
            for (int i = bags.length - 1; i >= 0; i--) {
                numCovered += bags[i].sumOfWeights();
                for (int j = 0; j < bags[i].numInstances(); j++) {
                    classDist[(int) bags[i].instance(j).classValue()] += bags[i].instance(j).weight();
                }

                int clIndex = getClassIndex(classDist);
                boolean stop = true;
                //for (int clIndex = 0; clIndex < localData.numClasses(); clIndex++) {
                    if (acceptableRule(classDist[clIndex], numCovered, localData.sumOfWeights())) {
                        JChipperRule rule = new JChipperRule(att, bags[i].instance(0).value(att), true, clIndex, classDist[clIndex], numCovered, classDist);
                        if (rule.betterThan(best)) {
                            best = rule;
                        }
                        stop = false;
                    }
                //}
                if (stop && m_beGreedy) {
                    break;
                }
            }
            if (best != null) {
                rules.add(best);
            }
            /** 
             * For numeric attributes 
             * Find best sequence of bags when using intervals
             */
            best = null;
            if (useInterval) {
				for (int j = 0; j < localData.numClasses(); j++) {
					classDist[j] = 0;
				}
                for (int i = 1; i < bags.length - 1; i++) {
                    for (int clIndex = 0; clIndex < localData.numClasses(); clIndex++) {
                        numCovered = bags[i].sumOfWeights();
                        for (int j = 0; j < bags[i].numInstances(); j++) {
                            classDist[(int) bags[i].instance(j).classValue()] += bags[i].instance(j).weight();
                        }
                        double numCorrect = classDist[(int) clIndex];
                        JChipperRule from = new JChipperRule(att, bags[i].instance(0).value(att), true, clIndex, -1, -1, null),
                                to = null;
                        for (int j = i + 1; j < bags.length; j++) {
                            boolean stop = true;
                            numCovered += bags[j].sumOfWeights();
                            for (int c = 0; c < bags[j].numInstances(); c++) {
                                classDist[(int) bags[j].instance(c).classValue()] += bags[j].instance(c).weight();
                            }
                            numCorrect = classDist[clIndex];
                            if (acceptableRule(numCorrect, numCovered, localData.sumOfWeights())) {
                                stop = false;
                                to = new JChipperRule(att, bags[j].instance(0).value(att), false, clIndex, -1, -1, null);
                                JChipperRule rule = new JChipperRule(from, to, numCorrect, numCovered, classDist, true);
                                if (rule.betterThan(best)) {
                                    best = rule;
                                }
                            }
                            if (stop && m_beGreedy) {
                                break;
                            }
                        }
                    }
                }
            }
            if (best != null) {
                rules.add(best);
            }
        }
        return rules;
    }

    private int getClassIndex(double[] classDist) {
    	int maxI = 0;
    	double maxD = -1;
    	for (int i = 0; i < classDist.length; i++)
    		if (i != m_majorityClass && classDist[i] > maxD) {
    			maxD = classDist[i];
    			maxI = i;
    		}    		
    	return maxI;
	}

	private List<JChipperRule> findChipperRule(ExecutorService executor, Instances localData, boolean useInterval) {
        List<JChipperRule> rules = new LinkedList<JChipperRule>();
    	for (Enumeration<Attribute> ea = localData.enumerateAttributes(); ea.hasMoreElements();) {
            //executor.execute(new ThreadedFindAttributeSplit(rules, localData, ea.nextElement(), useInterval));
            
            rules.addAll(findAttributeSplit(localData, ea.nextElement(), useInterval));
        }
        executor.shutdown();
        while(!executor.isTerminated()){
        }
        if (rules != null)
            Collections.sort(rules);
        return rules;
    }
    
    private class ThreadedFindAttributeSplit implements Runnable {
    	Instances data;
    	Attribute att;
    	boolean useInterval;
    	List<JChipperRule> rules;
    	
    	public ThreadedFindAttributeSplit(List<JChipperRule> list, Instances data, Attribute att, boolean useInterval) {
    		this.data = data;
    		this.att = att;
    		this.useInterval = useInterval;
    		this.rules = list;
    	}
    	
		@Override
		public void run() {
			rules.addAll(findAttributeSplit(data, att, useInterval));
		}
    	
    }

    /**
     * Generates a classifier.
     *
     * @param data set of instances serving as training data
     * @throws Exception if the classifier has not been generated
     *   successfully
     */
    @Override
    public void buildClassifier(Instances data) {
        data.deleteWithMissingClass();
        m_data = data;

        m_Model = new Vector();
        Instances localData = new Instances(data);

        m_ClassNames = new String[data.classAttribute().numValues()];
        for (int i = 0; i < data.classAttribute().numValues(); i++)
            m_ClassNames[i] = data.classAttribute().value(i);

        m_numInstances = data.sumOfWeights();
        priorDist = new double[data.numClasses()];
        for (int j = 0; j < data.numClasses(); j++) {
            priorDist[j] = 0;
        }
        for (int j = 0; j < data.numInstances(); j++) {
            priorDist[(int) data.instance(j).classValue()] += data.instance(j).weight();
        }
        for (int j = 0; j < data.numClasses(); j++) {
            priorDist[j] = priorDist[j]/data.sumOfWeights();
        }
        boolean isFinished = false;
        double totalCovered = 0;
        JChipperRule defaultRule = null;
        ExecutorService executor = Executors.newFixedThreadPool(Runtime.getRuntime().availableProcessors());
        
//        List<Instance> majorityInstances = null;
        if (m_useMajorityAsDefault) {
        	m_majorityClass = Utils.maxIndex(priorDist);
//        	majorityInstances = data.stringFreeStructure();
//        	for (int i = data.numInstances()-1; i >= 0; i--) {
//        		Instance instance = localData.instance(i);
//        		if (instance.classValue() == majorityClass) {
//        			majorityInstances.add(instance);
//        			localData.delete(i);
//        		}        			
//        	}
        }
        
        while (!isFinished) {
            JChipperRule bestRule = null;
            List<JChipperRule> rules = new LinkedList<JChipperRule>();
            rules = findChipperRule(executor, localData, m_useInterval);
            
            for (int i = 0; i < getNumConjunctions(); i++) {
                rules = findConjunctiveRules(executor, rules, localData);
            }
            if (getNumDisjunctions() > 0) {
                rules = findDisjunctiveRules(rules, localData);
            }

            bestRule = findBestRule(rules);

            /** If any rule was found, add it */
            if (bestRule != null) {
                m_Model.addElement(bestRule);
                totalCovered += bestRule.numCovered;

                /** remove classified instances */
                for (int i = localData.numInstances() - 1; i >= 0; i--) {
                    if (bestRule.covers(localData.instance(i))) {
                        localData.delete(i);
                    }
                }
            } else {
                isFinished = true;
            }

//            if (m_useMajorityAsDefault) {
//            	Instances defaultInstances = new Instances(localData);
//            	defaultInstances.addAll(majorityInstances);
//            	defaultRule = getDefaultRule(defaultInstances);
//            } else {
            	defaultRule = getDefaultRule(localData);
//            }

            if (totalCovered >= data.sumOfWeights() * m_stop || acceptableRule(defaultRule.numCorrect, defaultRule.numCovered, data.sumOfWeights())) {
                isFinished = true;
            }
        }
        m_Model.addElement(defaultRule);
    }

    /**
     * Classifies a given test instance using the rule set.
     *
     * @param instance the instance to be classified
     * @return the classification
     */
    @Override
    public double classifyInstance(Instance instance) throws Exception {

        if (m_Model == null) {
            throw new Exception("No JChipper classifier created yet!");
        }

        for (Enumeration<JChipperRule> ec = m_Model.elements(); ec.hasMoreElements();) {
            JChipperRule cr = ec.nextElement();
            if (cr.covers(instance)) {
                return cr.classify(instance);
            }
        }

        return -1;
    }

    /**
     * Computes class distribution for instance using rule set.
     *
     * @param instance the instance for which distribution is to be computed
     * @return the class distribution for the given instance
     * @todo implementera denna... Skall den implementeras
     */
    @Override
    public double[] distributionForInstance(Instance instance) throws Exception {

        if (m_Model == null) {
            throw new Exception("No JChipper classifier created yet!");
        }

        for (Enumeration<JChipperRule> ec = m_Model.elements(); ec.hasMoreElements();) {
            JChipperRule cr = ec.nextElement();
            if (cr.covers(instance)) {
                return cr.getDistribution(instance);
            }
        }
        /** Following lines will not be called unless something is wrong */
        double[] doubles = new double[instance.numClasses()];
        for (int i = 1; i < instance.numClasses(); i++) {
            doubles[i] = 0;
        }
        doubles[(int) ((JChipperRule) m_Model.lastElement()).classify(instance)] = 1;
        return doubles;
    }

    /**
     * Prints the rule set using the private toString method from below.
     *
     * @return a textual description of the classifier
     */
    @Override
    public String toString() {
        if (m_Model == null) {
            return "JChipper: No model built yet.";
        }
        StringBuffer sb = new StringBuffer("JChipper rules:\n" +
                "===========\n\n");
        for (int j = 0; j < m_Model.size(); j++) {
            JChipperRule rule = (JChipperRule) m_Model.elementAt(j);
            sb.append(rule.toString());
        }
        if (m_Debug) {
            System.err.println("Inside m_Model");
            for (int i = 0; i < m_Model.size(); i++) {
                System.err.println(((JChipperRule) m_Model.elementAt(i)).toString());
            }
        }
        sb.append("\nNumber of Rules      : " + m_Model.size());
        sb.append("\nNumber of Conditions : " + numConditions() + "\n");
        return sb.toString();
    }

    /**
     * Returns a string describing the classifier.
     * @return a description suitable for the GUI.
     * @todo skriv om instruktionerna...
     * till�ts saknade v�rden?
     * se vad? n�gon artikel kanske
     */
    public String globalInfo() {
        return "Class for constructing rule sets. For more " + "information see: \n\n" + "... ";
    }

  /**
   * Returns default capabilities of the classifier.
   *
   * @return      the capabilities of this classifier
   */
    @Override
  public Capabilities getCapabilities() {
    Capabilities result = new Capabilities(this);

    // attributes
    result.enable(Capability.NOMINAL_ATTRIBUTES);
    result.enable(Capability.NUMERIC_ATTRIBUTES);
    //result.enable(Capability.DATE_ATTRIBUTES);
    result.enable(Capability.MISSING_VALUES);

    // class
    result.enable(Capability.NOMINAL_CLASS);
    result.enable(Capability.MISSING_CLASS_VALUES);

    // instances
    result.setMinimumNumberInstances(1);

    return result;
  }

    /**
     * Returns an enumeration describing the available options.
     *
     * @return an enumeration of all the available options.
     */
    @Override
    public Enumeration listOptions() {

        Vector newVector = new Vector(8);

        newVector.addElement(new Option(
                "Beskriv", "D", 0, "-D"));
        newVector.addElement(new Option(
                "Beskriv", "C", 0, "-C"));
        newVector.addElement(new Option(
                "Beskriv", "I", 0, "-I"));
        newVector.addElement(new Option(
                "Beskriv", "G", 0, "-G"));
        newVector.addElement(new Option(
                "Beskriv", "R", 1, "-R < rule evaluation, [Coverage = 0, Accuracy = 1, Laplace = 2, M-estimate = 3, FOIL = 4] (1) >"));
        newVector.addElement(new Option(
                "Beskriv", "U", 1, "-U < Use of Ignore, [] (0) >"));
        newVector.addElement(new Option(
                "Beskriv, fr�gan hur denna skall implementeras �r inte helt sj�lvklart s� fr�gan �r om antalet argument (sista argumentet) skall avara 1, eller flera...",
                "P", 1, "-P beskriv synopsis"));
        newVector.addElement(new Option(
                "Beskriv",
                "S", 1, "-S beskriv synopsis"));

        return newVector.elements();
    }

    /**
     * Parses a given list of options. Valid options are:<p>
     *
     * -D  <br>
     * If set, classifier is run in debug mode and
     * may output additional info to the console.<p>
     *
     * @param options the list of options as an array of strings
     * @exception Exception if an option is not supported
     */
    @Override
    public void setOptions(String[] options) throws Exception {
        String tmp = Utils.getOption("D", options);
        if (tmp.length() != 0) {
            m_numDisjunctions = Integer.parseInt(tmp);
        }

        tmp = Utils.getOption("C", options);
        if (tmp.length() != 0) {
            m_numConjunctions = Integer.parseInt(tmp);
        }
        
        tmp = Utils.getOption("R", options);
        if (tmp.length() != 0)
            setRuleSelectionCriterion (
                    new SelectedTag (Integer.parseInt (tmp), TAGS_ruleSel));
        else
            setRuleSelectionCriterion (
                    new SelectedTag (m_ruleSelChoice, TAGS_ruleSel));

        
        tmp = Utils.getOption("U", options);
        if (tmp.length() != 0)
            setIgnoreSelection (
                    new SelectedTag (Integer.parseInt (tmp), TAGS_ignoreSel));
        else
            setIgnoreSelection (
                    new SelectedTag (m_ignoreSelChoice, TAGS_ignoreSel));


        int i = Utils.getOptionPos("I", options);
        if (i > -1) {
            m_useInterval = true;
            if (i + 1 < options.length) {
                tmp = options[i + 1];
                if (tmp.length() != 0 && !tmp.startsWith("-")) {
                    m_useInterval = Double.parseDouble(tmp) != 0;
                    options[i + 1] = "";
                }
            }
            options[i] = "";
        } else m_useInterval = false;
        
        m_beGreedy = Utils.getFlag('G', options);

        tmp = Utils.getOption("P", options);
        if (tmp.length() != 0) {
            m_ignoreVal = Double.parseDouble(tmp);
        }

        tmp = Utils.getOption("S", options);
        if (tmp.length() != 0) {
            m_stop = Double.parseDouble(tmp);
        }
    }

    /**
     * Gets the current settings of the Classifier.
     *
     * @return an array of strings suitable for passing to setOptions
     */
    @Override
    public String[] getOptions() {
        String[] options = new String[14];
        int current = 0;
        options[current++] = "-D";
        options[current++] = "" + m_numDisjunctions;

        options[current++] = "-C";
        options[current++] = "" + m_numConjunctions;

        options[current++] = "-R";
        options[current++] = "" + m_ruleSelChoice;
        options[current++] = "-U";
        options[current++] = "" + m_ignoreSelChoice;
        if (m_useInterval) {
            options[current++] = "-I";
        }
        if (m_beGreedy) {
            options[current++] = "-G";
        }

        /* @Todo Implementation m_ignoreProp? */
        options[current++] = "-P";
        options[current++] = "" + m_ignoreVal;
        options[current++] = "-S";
        options[current++] = "" + m_stop;


        while (current < options.length) {
            options[current++] = "";
        }

        return options;
    }

    /**
     *  Returns the type of graph this classifier
     *  represents.
     *  @return Drawable.TREE
     */
    public int graphType() {
        return Drawable.TREE;
    }

    /**
     * Returns graph describing the tree.
     *
     * @exception Exception if graph can't be computed
     */
    public String graph() throws Exception {

        return "";
    }

    /**
     * Returns tree in prefix order.
     *
     * @exception Exception if something goes wrong
     */
    public String prefix() throws Exception {

        return "";
    }

    /**
     * Returns a superconcise version of the m_Model
     * Exempel fr�n GREX
     */
    public String toSummaryString() {
        //Finns det n�gra extra m�tt som Chipper skall kunna producera?
        return "";
    }

    /**
     * Returns an enumeration of the additional measure names
     * @return an enumeration of the measure names
     */
    public Enumeration enumerateMeasures() {
        //Finns det n�gra extra m�tt som Chipper skall kunna producera?
        Vector newVector = new Vector(3);
        newVector.addElement("measureNumConditions");
        newVector.addElement("measureNumRules");
        newVector.addElement("measureRuleSetAccuracy");
        return newVector.elements();
    }

    /**
     * Returns the value of the named measure
     * @param measureName the name of the measure to query for its value
     * @return the value of the named measure
     * @exception IllegalArgumentException if the named measure is not supported
     */
    public double getMeasure(String additionalMeasureName) {
        /* Finns det n�gra extra m�tt som Chipper skall kunna producera? */
        if (additionalMeasureName.compareToIgnoreCase("measureNumConditions") == 0) {
        return numConditions();
        } else if (additionalMeasureName.compareToIgnoreCase("measureNumRules") == 0) {
        return m_Model.size();
        } else if (additionalMeasureName.compareToIgnoreCase("measureRuleSetAccuracy") == 0) {
        return 0;
        } else {
        throw new IllegalArgumentException(additionalMeasureName
        + " not supported (JChipper)");
        }
    }
    
    /**
     * Returns the tip text for this property
     * @return tip text for this property suitable for
     * displaying in the explorer/experimenter gui
     */
    public String ruleSelectionCriterionTipText() {
        return
                "...";
    }

    /**
     * Get the value of crt.
     *
     * @return Value of crt.
     */
    public SelectedTag getRuleSelectionCriterion() {

        return new SelectedTag(m_ruleSelChoice, TAGS_ruleSel);
    }

    /**
     * Set the value of crt.
     *
     * @param creationType Value to assign to crt.
     */
    public void setRuleSelectionCriterion(SelectedTag value) {
        if (value.getTags() == TAGS_ruleSel)
            m_ruleSelChoice = value.getSelectedTag().getID();
    }
    /**
     * Returns the tip text for this property
     * @return tip text for this property suitable for
     * displaying in the explorer/experimenter gui
     */
    public String ignoreSelectionTipText() {
        return
                "...";
    }

    /**
     * Get the value of crt.
     *
     * @return Value of crt.
     */
    public SelectedTag getIgnoreSelection() {

        return new SelectedTag(m_ignoreSelChoice, TAGS_ignoreSel);
    }

    /**
     * Set the value of crt.
     *
     * @param creationType Value to assign to crt.
     */
    public void setIgnoreSelection(SelectedTag value) {
        if (value.getTags() == TAGS_ignoreSel)
            m_ignoreSelChoice = value.getSelectedTag().getID();
    }

    /**
     * Get the value of m_useInterval.
     *
     * @return Value of m_useInterval.
     */
    public boolean getUseInterval() {

        return m_useInterval;
    }

    /**
     * Set the value of m_useInterval.
     *
     * @param tombola Value to assign to m_useInterval.
     */
    public void setUseInterval(boolean value) {

        m_useInterval = value;
    }

    /**
     * Returns the tip text for this property
     * @return tip text for this property suitable for
     * displaying in the explorer/experimenter gui
     */
    public String useIntervalTipText() {
        return "UseInterval?";
    }

    /**
     * Get the value of m_useInterval.
     *
     * @return Value of m_useInterval.
     */
    public boolean getBeGreedy() {

        return m_beGreedy;
    }

    /**
     * Set the value of m_useInterval.
     *
     * @param tombola Value to assign to m_useInterval.
     */
    public void setBeGreedy(boolean value) {

        m_beGreedy = value;
    }

    /**
     * Returns the tip text for this property
     * @return tip text for this property suitable for
     * displaying in the explorer/experimenter gui
     */
    public String beGreedyTipText() {
        return "BeGreedy for numeric attributes?";
    }

    /**
     * Get the value of m_useInterval.
     *
     * @return Value of m_useInterval.
     */
    public int getNumConjunctions() {
        return m_numConjunctions;
    }

    /**
     * Set the value of m_useInterval.
     *
     * @param tombola Value to assign to m_useInterval.
     */
    public void setNumConjunctions(int value) {
        m_numConjunctions = value;
    }

    /**
     * Returns the tip text for this property
     * @return tip text for this property suitable for
     * displaying in the explorer/experimenter gui
     */
    public String numConjunctionsTipText() {
        return "NumConjunctions?";
    }

    /**
     * Get the value of m_useInterval.
     *
     * @return Value of m_useInterval.
     */
    public int getNumDisjunctions() {
        return m_numDisjunctions;
    }

    /**
     * Set the value of m_useInterval.
     *
     * @param tombola Value to assign to m_useInterval.
     */
    public void setNumDisjunctions(int value) {
        m_numDisjunctions = value;
    }

    /**
     * Returns the tip text for this property
     * @return tip text for this property suitable for
     * displaying in the explorer/experimenter gui
     */
    public String numDisjunctionsTipText() {
        return "NumDisjunctions?";
    }

    /**
     * Get the value of m_stop.
     *
     * @return Value of m_stop.
     */
    public double getStop() {

        return m_stop;
    }

    /**
     * Set the value of m_stop.
     *
     * @param m_stop Value to assign to tra.
     */
    public void setStop(double value) {

        m_stop = value;
    }

    /**
     * Returns the tip text for this property
     * @return tip text for this property suitable for
     * displaying in the explorer/experimenter gui
     */
    public String stopTipText() {
        return "Beskriv percent";
    }

    /**
     * Get the value of m_ignoreProp.
     *
     * @return Value of m_ignoreProp.
     */
    public double getIgnore() {

        return m_ignoreVal;
    }

    /**
     * Set the value of m_ignoreProp.
     *
     * @param m_ignoreVal Value to assign to tra.
     */
    public void setIgnore(double value) {

        m_ignoreVal = value;
    }

    /**
     * Returns the tip text for this property
     * @return tip text for this property suitable for
     * displaying in the explorer/experimenter gui
     */
    public String ignoreTipText() {
        return "Beskriv Ignore";
    }

    /**
     * Main method.
     *
     * @param args the options for the classifier
     */
    public static void main(String[] args) {

        try {
            System.out.println(Evaluation.evaluateModel(new JChipper(), args));
        } catch (Exception e) {
            System.err.println(e.getMessage());
        }
    }
}
